<?php
/*
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。



示例 1：


输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：


输入：obstacleGrid = [[0,1],[0,0]]
输出：1


提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

https://leetcode-cn.com/problems/unique-paths-ii/

*/

$obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]];
$obstacleGrid = [[0,1]];
$o  = new Solution063();
$res = $o->main($obstacleGrid);
var_dump($res);

class Solution063
{
    // dp[i][j]：从(0, 0)出发到达(i, j)的路径数量
    public function main($grid)
    {
        $m  = count($grid);
        $n  = count($grid[0]);
        $dp = array_fill(0, $m, array_fill(0, $n, 0));
        for ($i = 0; $i < $m && $grid[$i][0] == 0; $i++) {
            $dp[$i][0] = 1;
        }
        for ($i = 0; $i < $n && $grid[0][$i] == 0; $i++) {
            $dp[0][$i] = 1;
        }
        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                // 坐标(i,j)没有障碍的时候才推导dp[i][j]
                if ($grid[$i][$j] == 0) {
                    $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
                }
            }
        }
        return $dp[$m - 1][$n - 1];
    }



}
